#include <string>
#include <iostream>
using namespace std;

struct Node
{
	char data;
	Node* lchild;
	Node* rchild;
};

Node* buildTree(string pre, string in)
{
	//递归结束和错误判断
	if (pre.size() == 0 || in.size() == 0 || pre.size() != in.size())
	{
		return NULL;
	}

	Node* root = new Node;
	root->data = pre[0];
	string pre_left,
		pre_right,
		in_left,
		in_right;
	int i,
		index = 0;

	//在中序遍历里面找到根节点
	for (i = 0; i < in.size(); i++)
	{
		if (root->data == in[i])
		{
			index = i;
		}
	}


	for (i = 0; i < index; i++)
	{
		pre_left.push_back(pre[i + 1]);//根节点左子树前序遍历序列
		in_left.push_back(in[i]);//根节点右左子树中序遍历序列
	}

	for (i = index + 1; i < pre.size(); i++)//在前序遍历里面找到根节点
	{
		pre_right.push_back(pre[i]);//根节点右子树前序遍历序列
		in_right.push_back(in[i]);//根节点右子树中序遍历序列
	}

	root->lchild = buildTree(pre_left, in_left);//递归构建左子树
	root->rchild = buildTree(pre_right, in_right);//递归构建右子树
	return root;

}

int High(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		int hl = High(root->lchild);
		int h2 = High(root->rchild);
		return (hl > h2 ? hl : h2) + 1;
	}
}

//后序遍历
void PostOrder(Node* root)
{
	if (root == NULL)
	{
		return;
	}

	PostOrder(root->lchild);
	PostOrder(root->rchild);
	cout << root->data;
}

int main()
{
	int i, n;
	cin >> n;
	string** strTree = new string * [n];
	if (!strTree)
	{
		cout << "内存申请错误！！！" << endl;
		return 1;
	}
	for (i = 0; i < n; i++)
	{
		strTree[i] = new string[2];
		if (!strTree[i])
		{
			cout << "内存申请错误！！！" << endl;
			return 1;
		}
		cin >> strTree[i][0] >> strTree[i][1];
	}

	for (i = 0; i < n; i++)
	{
		Node* root = buildTree(strTree[i][0], strTree[i][1]);
		cout << High(root) << " ";
		PostOrder(root);
		cout << endl;
	}

	system("pause");
	return 0;
}